from math import log
from sentence_cut.PredfixDict import get_prefix_dict
from sentence_cut.DAG import get_DAG
def clac(sentence, DAG, freq, total):
    n = len(sentence)
    route = {n: (0, 0)}
    log_total = log(total)

    for i in range(n-1, -1, -1):
        cache = []
        for j in DAG[i]:
            log_p = log(freq.get(sentence[i:j+1], 0) or 1)
            cache.append((log_p - log_total + route[j+1][0], j))
        route[i] = max(cache)
    return route

if __name__=="__main__":
    example = "我在学习结巴分词"
    freq, total = get_prefix_dict("./dict.txt")
    dag = get_DAG(example, freq)
    route = clac(example, dag, freq, total)
    print(route)